/*
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。
*/
package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{-1, 0, 1, 2, -1, -4}

	res := threeSum(nums)
	fmt.Println(res)
}

func threeSum(nums []int) [][]int {
	var results [][]int

	// 对切片进行排序--->从小到大
	sort.Ints(nums)

	for i := 0; i < len(nums); i++ {

		// 去重逻辑-->去掉重复的三元组
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		//定义左右指针
		left := i + 1
		right := len(nums) - 1

		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum == 0 {
				results = append(results, []int{nums[i], nums[left], nums[right]})

				// 去重逻辑
				for left < right && nums[left] == nums[left+1] {
					left++
				}
				for left < right && nums[right] == nums[right-1] {
					right--
				}

				left++
				right--
			} else if sum < 0 {
				left++
			} else {
				right--
			}
		}
	}

	return results
}
